package cn.z2huo.knowledge.concurrency.cas.lock;

import lombok.Data;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;

/**
 * <p>抢锁线程在队列尾部加入一个节点，然后仅在前驱节点上进行普通自旋，它不断轮询前一个节点状态，
 * 如果发现前一个节点释放锁，当前节点抢锁成功。
 *
 * @author z2huo
 */
class CLHLock implements Lock {

    /**
     * 节点线程本地变量
     * 获取到锁的线程才会向 ThreadLocal 中赋值
     */
    private static final ThreadLocal<Node> NODE_THREAD_LOCAL = new ThreadLocal<>();

    /**
     * CLHLock 队列的尾部指针，使用 AtomicReference，方便进行 CAS 操作
     */
    private final AtomicReference<Node> tail = new AtomicReference<>(null);

    public CLHLock() {
        // todo 这里有必要用 compareAndSet 吗？
        tail.set(Node.EMPTY_NODE);
    }

    /**
     * 加锁操作，将节点添加到等待队列的尾部
     */
    @Override
    public void lock() {
        // 抢锁时创建一个新的 Node 节点
        Node newNode = new Node(true, null);

        Node tailNode = tail.get();
        // CAS 自旋，将新创建的节点插入到队列的尾部，通过 CAS 自旋完成，以确保操作成功
        // 这里为什么要 CAS 自旋，自己给自己赋值，不能省略自旋，直接赋值新节点的前驱节点吗？
        // 测了一下，是不能省略的
        // 每一个线程在抢占锁时，都需要创建属于自己的 Node，所以 tail 会随着线程尝试获取锁而变化
        // 上面获取到了 tailNode 变量之后，需要将 tailNode 变量赋值给 newNode 的 prevNode，并且重新赋值尾节点
        // 这个获取和赋值的操作不是原子性的，中间可能会因为其他线程而发生尾节点的改变
        while (!tail.compareAndSet(tailNode, newNode)) {
            tailNode = tail.get();
        }
        // 设置前驱节点
        newNode.setPrevNode(tailNode);

//        Node tailNode = tail.get();
//        tail.set(newNode);
//        newNode.setPrevNode(tailNode);

        // 自旋，监听前驱节点的 locked 变量，直到其值为 false
        // 若前驱节点的 locked 为 true，表示有其他线程在占用或抢占锁
        // 若为 false，表示前驱节点释放了锁，当前线程可以抢占锁
        while (newNode.getPrevNode().isLocked()) {
            // 让出 CPU 时间片
            Thread.yield();
        }

        // 将当前节点缓存在线程本地变量中，释放锁时会用到
        NODE_THREAD_LOCAL.set(newNode);
    }

    /**
     * 释放锁
     */
    @Override
    public void unlock() {
        Node currNode = NODE_THREAD_LOCAL.get();
        currNode.setLocked(false);
        // 当前线程释放锁时，才会将当前线程的节点的前驱节点赋值为 null，以便 GC 可以回收前驱节点
        currNode.setPrevNode(null);
        // 为了使得线程下一次抢锁不会出错
        NODE_THREAD_LOCAL.set(null);
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {

    }

    @Override
    public boolean tryLock() {
        return false;
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        return false;
    }

    @Override
    public Condition newCondition() {
        return null;
    }

    /**
     * 虚拟等待队列的节点
     */
    @Data
    static class Node {

        /**
         * true 当前线程正在抢占锁，或者已经占有锁
         * false 当前线程已经释放锁，下一个线程可以占有锁了
         */
        private volatile boolean locked;

        /**
         * 前驱节点，当前节点需要监听前驱节点的 locked 字段
         */
        private Node prevNode;

        /**
         * 空节点
         */
        public static final Node EMPTY_NODE = new Node(false, null);

        public Node(boolean locked, Node prevNode) {
            this.locked = locked;
            this.prevNode = prevNode;
        }
    }

}
